package futu

// 定义一个双向链表节点
type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

// 定义一个LRU结构体
type LRU struct {
	capacity int            // 缓存容量
	size     int            // 缓存大小
	cache    map[int]*Node  // 哈希表
	head     *Node          // 链表头部
	tail     *Node          // 链表尾部
}

// 初始化一个LRU对象
func NewLRU(capacity int) *LRU {
	l := &LRU{
		capacity: capacity,
		size:     0,
		cache:    make(map[int]*Node),
		head:     &Node{},
		tail:     &Node{},
	}
	l.head.next = l.tail
	l.tail.prev = l.head
	return l
}

// 访问一个缓存中的数据
func (l *LRU) Get(key int) int {
	if node, ok := l.cache[key]; ok { // 如果键存在于哈希表中
		l.moveToHead(node)            // 将对应的节点移动到链表头部
		return node.value             // 返回对应的值
	}
	return -1 // 否则返回-1或者空值
}

// 插入或更新一个缓存中的数据
func (l *LRU) Put(key int, value int) {
	if node, ok := l.cache[key]; ok { // 如果键存在于哈希表中
		node.value = value            // 更新对应的节点值
		l.moveToHead(node)            // 将对应的节点移动到链表头部
	} else {                          // 否则
		node := &Node{                // 创建一个新的节点
			key:   key,
			value: value,
		}
		l.cache[key] = node           // 在哈希表中添加
		l.addToHead(node)            // 在链表头部添加
		l.size++                     // 缓存大小加一
		if l.size > l.capacity {     // 如果缓存空间已满
			removed := l.removeTail() // 删除链表尾部的节点
			delete(l.cache, removed.key) // 在哈希表中删除
			l.size--                  // 缓存大小减一
		}
	}
}

// 删除一个缓存中的数据
func (l *LRU) Delete(key int) {
	if node, ok := l.cache[key]; ok { // 如果键存在于哈希表中
		l.removeNode(node)            // 删除对应的链表节点
		delete(l.cache, key)          // 在哈希表中删除
		l.size--                      // 缓存大小减一
	}
}

// 将一个节点移动到链表头部
func (l *LRU) moveToHead(node *Node) {
	l.removeNode(node) // 先删除该节点
	l.addToHead(node)  // 再添加到头部
}

// 在链表头部添加一个节点
func (l *LRU) addToHead(node *Node) {
	node.prev = l.head           // 设置节点的前驱为头节点
	node.next = l.head.next      // 设置节点的后继为头节点的后继
	l.head.next.prev = node      // 设置头节点的后继的前驱为节点
	l.head.next = node           // 设置头节点的后继为节点
}

// 删除一个链表中的节点
func (l *LRU) removeNode(node *Node) {
	node.prev.next = node.next   // 设置节点的前驱的后继为节点的后继
	node.next.prev = node.prev   // 设置节点的后继的前驱为节点的前驱
}

// 删除链表尾部的节点并返回该节点
func (l *LRU) removeTail() *Node {
	node := l.tail.prev          // 获取尾部节点的前驱，即最后一个有效节点
	l.removeNode(node)           // 删除该节点
	return node                  // 返回该节点
}
